package offer;

import java.util.*;

public class Solution {

    /**
     * LCR 120. 寻找文件副本
     *
     * @param documents
     * @return
     */
    public int findRepeatDocument(int[] documents) {
        Set<Integer> set = new HashSet<>();

        for (int document : documents) {
            if (set.contains(document)) {
                return document;
            }
            set.add(document);
        }

        return -1;
    }

    /**
     * LCR 121. 寻找目标值 - 二维数组、
     * 右上角开始遍历
     *
     * @param plants
     * @param target
     * @return
     */
    public boolean findTargetIn2DPlants(int[][] plants, int target) {
        int m = plants.length;
        if (m == 0) {
            return false;
        }
        int n = plants[0].length;


        int i = 0, j = n - 1;

        while (i < m && j >= 0) {
            if (target < plants[i][j]) {
                j--;
            } else if (target > plants[i][j]) {
                i++;
            } else {
                return true;
            }
        }

        return false;
    }

    /**
     * LCR 122. 路径加密
     *
     * @param path
     * @return
     */
    public String pathEncryption(String path) {
        StringBuilder sb = new StringBuilder();

        for (char ch : path.toCharArray()) {
            if (ch == '.') {
                sb.append(" ");
            } else {
                sb.append(ch);
            }
        }

        return sb.toString();
    }

    /**
     * LCR 123. 图书整理 I
     *
     * @param head
     * @return
     */
    public int[] reverseBookList(ListNode head) {
        Stack<Integer> stack = new Stack<>();
        while (head != null) {
            stack.push(head.val);
            head = head.next;
        }
        int[] result = new int[stack.size()];
        for (int i = 0; i < result.length; i++) {
            result[i] = stack.pop();
        }
        return result;
    }

    /**
     * LCR 124. 推理二叉树
     * 剑指 Offer 07. 重建二叉树[前序+中序]
     *
     * @param preorder
     * @param inorder
     * @return
     */
    private final Map<Integer, Integer> map = new HashMap<>();

    public TreeNode deduceTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return buildTree(preorder, 0, inorder, 0, inorder.length - 1);
    }

    private TreeNode buildTree(int[] preorder, int preBegin, int[] inorder, int inBegin, int inEnd) {
        if (inBegin > inEnd || preBegin >= preorder.length) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[preBegin]);

        int index = map.get(preorder[preBegin]);
        root.left = buildTree(preorder, preBegin + 1, inorder, inBegin, index - 1);
        root.right = buildTree(preorder, preBegin + (index - inBegin) + 1, inorder, index + 1, inEnd);

        return root;
    }

    /**
     * LCR 129. 字母迷宫
     * 79. 单词搜索
     * 需要对已经使用过的字符进行标记
     *
     * @param grid
     * @param target
     * @return
     */
    public boolean wordPuzzle(char[][] grid, String target) {
        int m = grid.length;
        int n = grid[0].length;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dfs(grid, i, j, target, 0)) {
                    return true;
                }
            }
        }

        return false;
    }

    private boolean dfs(char[][] grid, int i, int j, String target, int index) {
        if (index >= target.length()) {
            return true;
        }
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length) {
            return false;
        }
        if (grid[i][j] == target.charAt(index)) {
            char cur = grid[i][j];
            grid[i][j] = ' ';
            boolean result = dfs(grid, i + 1, j, target, index + 1) || dfs(grid, i, j + 1, target, index + 1)
                    || dfs(grid, i - 1, j, target, index + 1) || dfs(grid, i, j - 1, target, index + 1);
            grid[i][j] = cur;
            return result;
        }
        return false;
    }

    /**
     * LCR 130. 衣橱整理
     * 剑指 Offer 13. 机器人的运动范围
     *
     * @param m
     * @param n
     * @param k
     * @return
     */
    public int wardrobeFinishing(int m, int n, int k) {
        boolean[][] visited = new boolean[m][n];
        return dfs(visited, 0, 0, m, n, k);
    }

    private int dfs(boolean[][] visited, int i, int j, int m, int n, int k) {
        if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j] || digitSum(i) + digitSum(j) > k) {
            return 0;
        }

        visited[i][j] = true;

        return 1 + dfs(visited, i + 1, j, m, n, k)
                + dfs(visited, i, j + 1, m, n, k);
    }

    private int digitSum(int num) {
        int sum = 0;
        while (num > 0) {
            sum += num % 10;
            num /= 10;
        }
        return sum;
    }

    /**
     * LCR 131. 砍竹子 I
     * 剑指 Offer 14- I. 剪绳子
     * 343. 整数拆分
     * 两种情况，剩下的（i - j）部分继续剪或者不剪直接使用
     *
     * @param n
     * @return
     */
    public int cuttingBamboo(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 1;

        for (int i = 3; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
            }
        }
        return dp[n];
    }

    /**
     * 上题的dfs版本解法
     *
     * @param n
     * @return
     */
    public int cuttingBamboo2(int n) {
        if (n <= 3) {
            return n - 1;
        }
        int[] result = new int[n];
        return dfs(n, result);
    }

    private int dfs(int n, int[] result) {
        // 因为 n<=4时，选择不剪的情况往往是更优的，一定比选择剪的结果要长
        if (n <= 4) {
            return n;
        }

        if (result[n - 1] != 0) {
            return result[n - 1];
        }

        int max = 0;
        for (int i = 1; i < n; i++) {
            max = Math.max(max, Math.max(i * (n - i), i * dfs(n - i, result)));
        }
        result[n - 1] = max;
        return max;
    }

    /**
     * 最优解：使用贪心，尽可能裁更多的3
     *
     * @param n
     * @return
     */
    public int cuttingBamboo3(int n) {
        if (n <= 3) return n - 1;
        int res = 1;
        while (n > 4) {
            res *= 3;
            n -= 3;
        }
        return res * n;
    }

    /**
     * LCR 133. 位 1 的个数
     * 技巧：n & (n-1)可以消除最右边的1
     *
     * @param n
     * @return
     */
    public int hammingWeight(int n) {
        int res = 0;
        while (n != 0) {
            res++;
            n = n & (n - 1);
        }
        return res;
    }

    /**
     * LCR 134. Pow(x, n)
     * 50. Pow(x, n)
     * 分治的方法，把n次方拆分成一个个平分
     *
     * @param x
     * @param n
     * @return
     */
    public static double myPow(double x, int n) {
        long N = n;
        return N >= 0 ? quickPowIter(x, N) : 1.0 / quickPowIter(x, -N);
    }

    private static double quickPowIter(double x, long n) {
        double result = 1.0;
        double current = x;
        for (long i = n; i > 0; i /= 2) {
            if (i % 2 == 1) {
                result *= current;
            }
            current *= current;
        }
        return result;
    }

    /**
     * 剑指 Offer 17. 打印从1到最大的n位数
     * 需要考虑大数问题，因此使用dfs全排列的方法
     *
     * @param n
     */
    public static void printNumbers(int n) {
        if (n <= 0) return;
        char[] array = new char[n];

        dfsNumber(array, 0);
    }

    private static void dfsNumber(char[] array, int index) {
        if (index == array.length) {
            printNum(array);
            return;
        }

        for (int i = 0; i <= 9; i++) {
            array[index] = (char) (i + '0');
            dfsNumber(array, index + 1);
        }
    }

    private static void printNum(char[] array) {
        int index = 0;

        while (index < array.length && array[index] == '0') {
            index++;
        }

        for (int i = index; i < array.length; i++) {
            System.out.print(array[i]);
        }
        System.out.println();
    }

    /**
     * LCR 136. 删除链表的节点
     *
     * @param head
     * @param val
     * @return
     */
    public ListNode deleteNode(ListNode head, int val) {
        if (head == null) {
            return null;
        }
        if (head.val == val) {
            return head.next;
        }
        ListNode prev = head;
        ListNode cur = head.next;
        while (cur != null) {
            if (cur.val == val) {
                prev.next = cur.next;
                break;
            }
            prev = cur;
            cur = cur.next;
        }
        return head;
    }

    /**
     * 10. 正则表达式匹配
     * LCR 137. 模糊搜索验证
     *
     * @param s
     * @param p
     * @return
     */
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for (int j = 1; j <= n; j++) {
            if (p.charAt(j - 1) == '*') {
                dp[0][j] = dp[0][j - 2];
            }
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                char sc = s.charAt(i - 1);
                char pc = p.charAt(j - 1);
                if (sc == pc || pc == '.') {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (pc == '*') {
                    if (sc == p.charAt(j - 2) || p.charAt(j - 2) == '.') {
                        dp[i][j] = dp[i - 1][j] || dp[i][j - 2];
                    } else {
                        dp[i][j] = dp[i][j - 2];
                    }
                }
            }
        }

        return dp[m][n];
    }

    /**
     * LCR 138. 有效数字
     * 剑指 Offer 20. 表示数值的字符串
     * 有限状态机（DFA）方法
     *
     * @param s
     * @return
     */
    public boolean validNumber(String s) {
        if (s == null || s.isEmpty()) {
            return false;
        }

        // 去掉首尾空格
        s = s.trim();

        // 标志位
        boolean hasNum = false; // 是否有数字
        boolean hasDot = false; // 是否有小数点
        boolean hasE = false;   // 是否有 e/E

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            if (Character.isDigit(c)) {
                // 当前字符是数字
                hasNum = true;
            } else if (c == '.') {
                // 小数点只能出现一次，并且不能出现在 e/E 后面
                if (hasDot || hasE) {
                    return false;
                }
                hasDot = true;
            } else if (c == 'e' || c == 'E') {
                // e/E 只能出现一次，并且前面必须有数字
                if (hasE || !hasNum) {
                    return false;
                }
                hasE = true;

                // 重置标志位，因为 e/E 后面需要重新判断是否有数字
                hasNum = false;
            } else if (c == '+' || c == '-') {
                // 正负号只能出现在开头，或者 e/E 的后面
                if (i != 0 && s.charAt(i - 1) != 'e' && s.charAt(i - 1) != 'E') {
                    return false;
                }
            } else {
                // 非法字符
                return false;
            }
        }

        // 最终必须有数字才是合法数值
        return hasNum;
    }

    /**
     * LCR 139. 训练计划 I
     * 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
     *
     * @param actions
     * @return
     */
    public int[] trainingPlan(int[] actions) {
        int left = 0, right = 0;

        while (right < actions.length) {
            if (actions[right] % 2 == 1) {
                int temp = actions[left];
                actions[left] = actions[right];
                actions[right] = temp;
                left++;
            }

            right++;
        }

        return actions;
    }

    /**
     * LCR 140. 训练计划 II
     * 剑指 Offer 22. 链表中倒数第k个节点
     *
     * @param head
     * @param cnt
     * @return
     */
    public ListNode trainingPlan(ListNode head, int cnt) {
        ListNode slow = head, fast = head;
        while (cnt > 0) {
            fast = fast.next;
            cnt--;
        }

        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }

        return slow;
    }

    /**
     * LCR 141. 训练计划 III
     * 剑指 Offer 24. 反转链表
     *
     * @param head
     * @return
     */
    public ListNode trainningPlan(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode prev = null, cur = head, next = null;

        while (cur != null) {
            next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }

    /**
     * LCR 142. 训练计划 IV
     * 剑指 Offer 25. 合并两个排序的链表
     *
     * @param l1
     * @param l2
     * @return
     */
    public ListNode trainningPlan(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-101);
        ListNode cur = dummy;
        ListNode cur1 = l1, cur2 = l2;

        while (cur1 != null && cur2 != null) {
            if (cur1.val < cur2.val) {
                cur.next = cur1;
                cur1 = cur1.next;
            } else {
                cur.next = cur2;
                cur2 = cur2.next;
            }
            cur = cur.next;
        }

        if (cur1 == null) {
            cur.next = cur2;
        } else {
            cur.next = cur1;
        }

        return dummy.next;
    }

    /**
     * LCR 143. 子结构判断
     * 剑指 Offer 26. 树的子结构
     * 用原函数递归寻找符合的根节点，另写一个辅助函数用于遍历对比整个树
     *
     * @param A
     * @param B
     * @return
     */
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) {
            return false;
        }
        return dfs(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }

    private boolean dfs(TreeNode A, TreeNode B) {
        if (B == null) {
            return true;
        }
        if (A == null || A.val != B.val) {
            return false;
        }

        return dfs(A.left, B.left) && dfs(A.right, B.right);
    }

    /**
     * LCR 144. 翻转二叉树
     * 剑指 Offer 27. 二叉树的镜像
     *
     * @param root
     */
    public void flipTree(TreeNode root) {
        if (root == null) {
            return;
        }
        flipTree(root.left);
        flipTree(root.right);
        swap(root);
    }

    private void swap(TreeNode root) {
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
    }

    /**
     * LCR 145. 判断对称二叉树
     *
     * @param root
     * @return
     */
    public boolean checkSymmetricTree(TreeNode root) {
        if (root == null) {
            return true;
        }
        return check(root.left, root.right);
    }

    private boolean check(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        }
        if (left == null || right == null) {
            return false;
        }
        if (left.val != right.val) {
            return false;
        }

        return check(left.left, right.right) && check(left.right, right.left);
    }

    /**
     * LCR 146. 螺旋遍历二维数组
     *
     * @param array
     * @return
     */
    public int[] spiralArray(int[][] array) {
        int m = array.length;
        if (m == 0) {
            return new int[0];
        }
        int n = array[0].length;
        int[] result = new int[m * n];
        int index = 0;
        int top = 0, bottom = m - 1, left = 0, right = n - 1;

        while (top < bottom && left < right) {

            for (int i = left; i < right; i++) {
                result[index++] = array[top][i];
            }

            for (int i = top; i < bottom; i++) {
                result[index++] = array[i][right];
            }

            for (int i = right; i > left; i--) {
                result[index++] = array[bottom][i];
            }

            for (int i = bottom; i > top; i--) {
                result[index++] = array[i][left];
            }

            top++;
            bottom--;
            left++;
            right--;
        }

        if (left == right && top == bottom) {
            result[index] = array[top][left];
        } else if (left == right) {
            while (top <= bottom) {
                result[index++] = array[top++][left];
            }
        } else if (top == bottom) {
            while (left <= right) {
                result[index++] = array[top][left++];
            }
        }

        return result;
    }

    /**
     * LCR 148. 验证图书取出顺序
     * 剑指 Offer 31. 栈的压入、弹出序列
     *
     * @param putIn
     * @param takeOut
     * @return
     */
    public boolean validateBookSequences(int[] putIn, int[] takeOut) {
        Stack<Integer> stack = new Stack<>();
        int index = 0;

        for (int num : putIn) {
            stack.push(num);

            while (!stack.isEmpty() && stack.peek() == takeOut[index]) {
                stack.pop();
                index++;
            }
        }
        return stack.isEmpty();
    }

    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    /**
     * LCR 153. 二叉树中和为目标值的路径
     *
     * @param root
     * @param target
     * @return
     */
    public List<List<Integer>> pathTarget(TreeNode root, int target) {
        findPath(root, target);
        return result;
    }

    private void findPath(TreeNode root, int target) {
        if (root == null) {
            return;
        }
        path.add(root.val);
        target -= root.val;
        if (target == 0 && root.left == null && root.right == null) {
            result.add(new ArrayList<>(path));
        } else {
            findPath(root.left, target);
            findPath(root.right, target);
        }

        path.remove(path.size() - 1);
    }


    List<String> res = new ArrayList<>();
    boolean[] isused;

    /**
     * LCR 157. 套餐内商品的排列顺序
     * 剑指 Offer 38. 字符串的排列
     *
     * @param goods
     * @return
     */
    public String[] goodsOrder(String goods) {
        isused = new boolean[goods.length()];
        char[] chars = goods.toCharArray();
        Arrays.sort(chars);
        backtracking(chars, new StringBuilder());
        return res.toArray(new String[0]);
    }

    private void backtracking(char[] chars, StringBuilder path) {
        if (path.length() == chars.length) {
            res.add(path.toString());
            return;
        }

        for (int i = 0; i < chars.length; i++) {
            if (isused[i] || (i > 0 && chars[i] == chars[i - 1] && !isused[i - 1])) {
                continue;
            }

            path.append(chars[i]);
            isused[i] = true;
            backtracking(chars, path);
            path.deleteCharAt(path.length() - 1);
            isused[i] = false;
        }
    }

    /**
     * LCR 161. 连续天数的最高销售额
     * 剑指 Offer 42. 连续子数组的最大和
     *
     * @param nums
     * @return
     */
    public int maxSales(int[] nums) {
        int res = nums[0];
        int pre = nums[0];
        for (int i = 1; i < nums.length; i++) {
            pre = Math.max(pre + nums[i], nums[i]);
            res = Math.max(res, pre);
        }
        return res;
    }

    /**
     * 233. 数字 1 的个数
     * 剑指 Offer 43. 1～n 整数中 1 出现的次数
     *
     * @param n
     * @return
     */
    public static int countDigitOne(int n) {
        int count = 0;
        for (long i = 1; i <= n; i *= 10) {
            long divider = i * 10;
            count += (n / divider) * i + Math.min(Math.max(n % divider - i + 1, 0), i);
        }
        return count;
    }

    /**
     * LCR 163. 找到第 k 位数字
     * 剑指 Offer 44. 数字序列中某一位的数字
     *
     * @param k
     * @return
     */
    public int findKthNumber(int k) {
        if (k <= 9) {
            return k;
        }
        long count = 9, start = 1;
        int n = 1;
        while (k > count) {
            k -= count;
            n++;
            start *= 10;
            count = 9 * n * start;
        }

        long num = start + (k - 1) / n;
        int pos = (k - 1) % n;

        return String.valueOf(num).charAt(pos) - '0';
    }

    /**
     * LCR 164. 破解闯关密码
     * 剑指 Offer 45. 把数组排成最小的数
     * 贪心，先转化成字符串数组，再设置一个排序
     *
     * @param password
     * @return
     */
    public String crackPassword(int[] password) {
        String[] strs = new String[password.length];

        for (int i = 0; i < password.length; i++) {
            strs[i] = String.valueOf(password[i]);
        }

        Arrays.sort(strs, (a, b) -> (a + b).compareTo(b + a));

        StringBuilder result = new StringBuilder();

        for (String str : strs) {
            result.append(str);
        }

        return result.toString();
    }

    /**
     * LCR 165. 解密数字
     * 剑指 Offer 46. 把数字翻译成字符串
     *
     * @param ciphertext
     * @return
     */
    public static int crackNumber(int ciphertext) {
        String s = String.valueOf(ciphertext);
        int[] dp = new int[s.length() + 1];
        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i <= s.length(); i++) {
            dp[i] = dp[i - 1];
            int cur = Integer.parseInt(s.substring(i - 2, i));
            if (cur >= 10 && cur < 26) {
                dp[i] += dp[i - 2];
            }
        }

        return dp[s.length()];
    }

    /**
     * LCR 166. 珠宝的最高价值
     *
     * @param frame
     * @return
     */
    public int jewelleryValue(int[][] frame) {
        int m = frame.length, n = frame[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = frame[0][0];
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i - 1][0] + frame[i][0];
        }
        for (int i = 1; i < n; i++) {
            dp[0][i] = dp[0][i - 1] + frame[0][i];
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + frame[i][j];
            }
        }

        return dp[m - 1][n - 1];
    }

    /**
     * LCR 167. 招式拆解 I
     * 剑指 Offer 48. 最长不含重复字符的子字符串
     *
     * @param arr
     * @return
     */
    public int dismantlingAction(String arr) {
        if (arr.length() == 0) {
            return 0;
        }
        char[] array = arr.toCharArray();
        Set<Character> set = new HashSet<>();
        int result = 1;
        int left = 0, right = 0;

        while (right < array.length) {
            if (set.contains(array[right])) {
                set.remove(array[left]);
                left++;
            } else {
                set.add(array[right]);
                result = Math.max(result, right - left + 1);
                right++;
            }
        }

        return result;
    }

    /**
     * LCR 168. 丑数
     * 三指针 + 动态规划按顺序找到每一个丑数，因为抽数的质因数只能是2，3，5，所以下一个丑数肯定是之前的丑数 *2 或*3 或*5得到的
     *
     * @param n
     * @return
     */
    public int nthUglyNumber(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1; // 第一个丑数是 1
        int p2 = 1, p3 = 1, p5 = 1; // 三个指针初始指向 dp[1]

        for (int i = 2; i <= n; i++) {
            int num2 = dp[p2] * 2;
            int num3 = dp[p3] * 3;
            int num5 = dp[p5] * 5;
            dp[i] = Math.min(num2, Math.min(num3, num5));

            // 移动生成当前丑数的指针（去重）
            if (dp[i] == num2) p2++;
            if (dp[i] == num3) p3++;
            if (dp[i] == num5) p5++;
        }
        return dp[n];
    }

    /**
     * 剑指 Offer 50. 第一个只出现一次的字符
     * LCR 169. 招式拆解 II
     *
     * @param arr
     * @return
     */
    public char dismantlingAction2(String arr) {
        int[] count = new int[26];

        for (char ch : arr.toCharArray()) {
            count[ch - 'a']++;
        }

        for (char ch : arr.toCharArray()) {
            if (count[ch - 'a'] == 1) {
                return ch;
            }
        }

        return ' ';
    }

    /**
     * LCR 170. 交易逆序对的总数
     * 剑指 Offer 51. 数组中的逆序对
     * 归并排序
     *
     * @param record
     * @return
     */
    private int count = 0;

    public int reversePairs(int[] record) {
        if (record == null || record.length == 0) {
            return count;
        }
        mergeSort(record, 0, record.length - 1);
        return count;
    }

    private void mergeSort(int[] record, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = left + (right - left) / 2;

        mergeSort(record, left, mid);
        mergeSort(record, mid + 1, right);

        merge(record, left, mid, right);
    }

    private void merge(int[] record, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int i = left, j = mid + 1, index = 0;

        while (i <= mid && j <= right) {
            if (record[i] <= record[j]) {
                temp[index++] = record[i++];
            } else {
                count += (mid - i + 1);
                temp[index++] = record[j++];
            }
        }

        while (i <= mid) {
            temp[index++] = record[i++];
        }

        while (j <= right) {
            temp[index++] = record[j++];
        }

        System.arraycopy(temp, 0, record, left, temp.length);
    }

    /**
     * 剑指 Offer 52. 两个链表的第一个公共节点
     * LCR 171. 训练计划 V
     * 双指针法
     *
     * @param headA
     * @param headB
     * @return
     */
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }

        ListNode pA = headA, pB = headB;

        while (pA != pB) {
            if (pA == null) {
                pA = headB;
            } else {
                pA = pA.next;
            }

            if (pB == null) {
                pB = headA;
            } else {
                pB = pB.next;
            }
        }

        return pA;
    }

    /**
     * LCR 172. 统计目标成绩的出现次数
     * 剑指 Offer 53 - I. 在排序数组中查找数字 I
     *
     * @param scores
     * @param target
     * @return
     */
    public int countTarget(int[] scores, int target) {
        int left = 0, right = scores.length - 1, mid = 0;

        while (left < right) {
            mid = left + (right - left) / 2;
            if (scores[mid] < target) {
                left = mid + 1;
            } else if (scores[mid] > target) {
                right = mid - 1;
            } else {
                break;
            }
        }

        if (left > right || (left == right && scores[left] != target)) {
            return 0;
        }

        if (left == right && scores[left] == target) {
            return 1;
        }

        int start = mid, end = mid;
        while (start >= 0 && scores[start] == target) {
            start--;
        }

        while (end <= scores.length - 1 && scores[end] == target) {
            end++;
        }

        return end - start - 1;
    }

    /**
     * LCR 173. 点名
     * 剑指 Offer 53 - II. 0～n-1中缺失的数字
     * 二分查找
     *
     * @param records
     * @return
     */
    public int takeAttendance(int[] records) {
        int left = 0, right = records.length - 1;

        if (right == 0 && records[0] == 0) {
            return 1;
        }

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (records[mid] == mid) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return left;
    }

    private int count2;
    private int result2 = 0;

    /**
     * LCR 174. 寻找二叉搜索树中的目标节点
     * 剑指 Offer 54. 二叉搜索树的第k大节点
     * 逆中序遍历
     *
     * @param root
     * @param cnt
     * @return
     */
    public int findTargetNode(TreeNode root, int cnt) {
        count = cnt;
        dfs(root);
        return result2;
    }

    private void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        dfs(root.right);
        if (--count == 0) {
            result2 = root.val;
            return;
        }
        dfs(root.left);
    }

    /**
     * LCR 175. 计算二叉树的深度
     * 剑指 Offer 55 - I. 二叉树的深度
     *
     * @param root
     * @return
     */
    public int calculateDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        return Math.max(calculateDepth(root.left), calculateDepth(root.right)) + 1;
    }

    /**
     * 剑指 Offer 55 - II. 平衡二叉树
     * 辅助函数后序遍历计算树的高度，每次计算都检查左右高度差是否为-1
     *
     * @param root
     * @return
     */
    public boolean isBalanced(TreeNode root) {
        return getHeight(root) != -1;
    }

    private int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);

        if (leftHeight == -1 || rightHeight == -1) {
            return -1;
        }

        if (Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        }

        return Math.max(leftHeight, rightHeight) + 1;
    }

    /**
     * 剑指 Offer 56 - I. 数组中数字出现的次数
     * LCR 177. 撞色搭配
     * 位运算技巧
     *
     * @param nums
     * @return
     */
    public int[] sockCollocation(int[] nums) {
        // 得到两个只出现一次的数字的异或结果
        int xorResult = 0;
        for (int num : nums) {
            xorResult ^= num;
        }

        // 找到xorResult中第一个为1的位
        // 因为xorResult是目标两个数的异或结果，为1说明这两个数在这个位置不相同，由此可以根据这个位将数组分为两组
        int mask = 1;
        while ((xorResult & mask) == 0) {
            mask <<= 1;
        }

        // 根据mask将数组分成两组，分别异或
        int a = 0, b = 0;
        for (int num : nums) {
            if ((num & mask) == 0) {
                a ^= num;
            } else {
                b ^= num;
            }
        }

        return new int[]{a, b};
    }

    /**
     * LCR 178. 训练计划 VI
     * 剑指 Offer 56 - II. 数组中数字出现的次数 II
     * 因为除目标数以外，每个数都出现三次，所以累积后每一位都应该可以被3整除，不能被整除的就是目标数的为1的位
     *
     * @param nums
     * @return
     */
    public int trainingPlan2(int[] nums) {
        int[] counts = new int[32];
        for (int num : nums) {
            for (int j = 0; j < 32; j++) {
                counts[j] += num & 1; // 统计每一位的1的个数
                num >>>= 1; // 无符号右移
            }
        }
        int res = 0;
        for (int i = 0; i < 32; i++) {
            res <<= 1; // 左移一位
            res |= counts[31 - i] % 3; // 从高位开始恢复
        }
        return res;
    }

    /**
     * LCR 179. 查找总价格为目标值的两个商品
     * 剑指 Offer 57. 和为s的两个数字
     *
     * @param price
     * @param target
     * @return
     */
    public int[] twoSum(int[] price, int target) {
        int[] result = new int[2];
        int left = 0, right = price.length - 1;

        while (left < right) {
            if (price[left] + price[right] > target) {
                right--;
            } else if (price[left] + price[right] < target) {
                left++;
            } else {
                result[0] = price[left];
                result[1] = price[right];
                return result;
            }
        }

        return result;
    }

    public int[][] fileCombination(int target) {
        List<int[]> res = new ArrayList<>();
        int left = 1, right = 2, cur = 3;

        while (left < right) {
            if (cur > target) {
                cur -= left;
                left++;
            } else if (cur < target) {
                right++;
                cur += right;
            } else {
                int[] path = new int[right - left + 1];
                for (int i = 0; i < path.length; i++) {
                    path[i] = left + i;
                }
                res.add(path);

                cur -= left;
                left++;
            }
        }

        return res.toArray(new int[res.size()][]);
    }

    /**
     * 剑指 Offer 58 - I. 翻转单词顺序
     *
     * @param message
     * @return
     */
    public String reverseMessage(String message) {
        message = message.trim();
        StringBuilder result = new StringBuilder();
        int i = message.length() - 1;
        int j = i;

        while (i >= 0) {
            while (i >= 0 && message.charAt(i) != ' ') {
                i--;
            }
            result.append(message, i + 1, j + 1);
            result.append(' ');
            while (i >= 0 && message.charAt(i) == ' ') {
                i--;
            }
            j = i;
        }
        return result.toString().trim();
    }

    /**
     * 剑指 Offer 58 - II. 左旋转字符串
     *
     * @param password
     * @param target
     * @return
     */
    public String dynamicPassword(String password, int target) {
        String s1 = password.substring(0, target);
        String s2 = password.substring(target);
        return s2 + s1;
    }

    /**
     * LCR 183. 望远镜中最高的海拔
     * 剑指 Offer 59 - I. 滑动窗口的最大值
     * 双端队列Deque，存放索引，一端用于确定最大值，一端用于确定当前的遍历位置
     *
     * @param nums
     * @param k
     * @return
     */
    public int[] maxAltitude(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0) {
            return new int[0];
        }

        int n = nums.length;
        int[] result = new int[n - k + 1];
        Deque<Integer> deque = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            // 移除不在窗口范围内的元素
            while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                deque.pollFirst();
            }

            // 维护单调递减队列
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }

            deque.offerLast(i);

            // 当窗口形成时记录结果
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peekFirst()];
            }
        }

        return result;
    }

    /**
     * 剑指 Offer 61. 扑克牌中的顺子
     *
     * @param nums
     * @return
     */
    public boolean checkDynasty(int[] nums) {
        Arrays.sort(nums);
        int zeroCount = 0;

        // 统计大小王数量
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                zeroCount++;
            } else if (i > 0 && nums[i] == nums[i - 1]) {
                // 如果有非0的重复牌，直接返回false
                return false;
            }
        }

        // 最大值和最小值的差应该小于5
        return nums[nums.length - 1] - nums[zeroCount] < 5;
    }

    /**
     * 剑指 Offer 62. 圆圈中最后剩下的数字
     * 约瑟夫环问题
     *
     * @param num
     * @param target
     * @return
     */
    public int iceBreakingGame(int num, int target) {
        int last = 0;

        // 根据递推公式计算 f(n, m)
        for (int i = 2; i <= num; i++) {
            last = (last + target) % i;
        }

        return last;
    }

    public static void main(String[] args) {
        //System.out.println(countDigitOne(5689));
        System.out.println(crackNumber(2112));
    }
}

/**
 * LCR 125. 图书整理 II
 * 剑指 Offer 09. 用两个栈实现队列
 * 一个用于入栈，一个用于出栈
 */
class CQueue {

    private final Stack<Integer> stackIn;
    private final Stack<Integer> stackOut;

    public CQueue() {
        stackIn = new Stack<>();
        stackOut = new Stack<>();
    }

    public void appendTail(int value) {
        stackIn.push(value);
    }

    public int deleteHead() {
        if (stackOut.isEmpty()) {
            while (!stackIn.isEmpty()) {
                stackOut.push(stackIn.pop());
            }
        }
        return stackOut.isEmpty() ? -1 : stackOut.pop();
    }
}

/**
 * LCR 147. 最小栈
 * 剑指 Offer 30. 包含min函数的栈
 */
class MinStack {
    private final Stack<Integer> dataStack;
    private final Stack<Integer> minStack;

    public MinStack() {
        dataStack = new Stack<>();
        minStack = new Stack<>();
    }

    public void push(int val) {
        dataStack.push(val);
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        } else {
            minStack.push(minStack.peek());
        }
    }

    public void pop() {
        dataStack.pop();
        minStack.pop();
    }

    public int top() {
        return dataStack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}

/**
 * LCR 160. 数据流中的中位数
 * 大根堆存较小的一半，小根堆存较大的一半
 */
class MedianFinder {

    PriorityQueue<Integer> minHeap;
    PriorityQueue<Integer> maxHeap;

    public MedianFinder() {
        minHeap = new PriorityQueue<>();
        maxHeap = new PriorityQueue<>((a, b) -> b - a);
    }

    public void addNum(int num) {
        maxHeap.offer(num);
        minHeap.offer(maxHeap.poll());
        if (maxHeap.size() < minHeap.size() - 1) {
            maxHeap.offer(minHeap.poll());
        }
    }

    public double findMedian() {
        if (maxHeap.size() == minHeap.size()) {
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        } else {
            return minHeap.peek();
        }
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}